//给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 
//
// 两棵树重复是指它们具有相同的结构以及相同的结点值。 
//
// 示例 1： 
//
//         1
//       / \
//      2   3
//     /   / \
//    4   2   4
//       /
//      4
// 
//
// 下面是两个重复的子树： 
//
//       2
//     /
//    4
// 
//
// 和 
//
//     4
// 
//
// 因此，你需要以列表的形式返回上述重复子树的根结点。 
// 👍 327 👎 0


package leetcode.editor.cn;

//寻找重复的子树

import Entity.TreeNode;
import 分类.二叉树;

import java.util.*;

public class P652_寻找重复的子树 implements 二叉树 {
    public static void main(String[] args) {
        Solution solution = new P652_寻找重复的子树().new Solution();
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(2);
        TreeNode f = new TreeNode(4);
        TreeNode g = new TreeNode(4);
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        e.left = g;

        List<TreeNode> duplicateSubtrees = solution.findDuplicateSubtrees(a);
        System.out.println();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 思路：
         *  后序遍历二叉树 获取到二叉树的所有子树的序列化字符串
         *  保存并判断是否已出现，并获取出现的次数，
         *  如出现则次数加1 并加入结果集中
         *  如果没出现则放入map中进行计数，直到出现次数大于1
         * @param root 二叉树根节点
         * @return
         */
        private Map<String, Integer> mapCounter = new HashMap<>();
        private List<TreeNode> res = new ArrayList<>();
        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
            // 获取根节点的
            serialization(root);
            return res;
        }
  
        
        private String serialization(TreeNode root) {
            if (root == null) {
                return "#";
            }
            // 获取左右子树的样子
            String left = serialization(root.left);
            String right = serialization(root.right);
            // 进行组装
            String treeStr = root.val + "," + left + "," + right;
            Integer orDefault = mapCounter.getOrDefault(treeStr, 0);
            if (mapCounter.containsKey(treeStr) && orDefault == 1) {
                res.add(root);
            }
            mapCounter.put(treeStr, orDefault+1);
            return treeStr;
        }

      
    }
//leetcode submit region end(Prohibit modification and deletion)


}